// https://leetcode.cn/problems/unique-paths-ii/


#include <iostream>

using namespace std;

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
		int m = obstacleGrid.size();
		int n = obstacleGrid[0].size();
		int dp[m][n];
		if(obstacleGrid[m-1][n-1] == 1){
			return 0;
		}
		int flag = 0;
		for(int i = 0; i < m; i++){
			if(obstacleGrid[i][0] != 1 && flag == 0){
				dp[i][0] = 1;
			}else {
				flag = 1;
				dp[i][0] = 0;
			}
		}
		flag = 0;
		for(int j = 0; j < n; j++){
			if(obstacleGrid[0][j] != 1 && flag == 0){
				dp[0][j] = 1;
			}else {
				flag = 1;
				dp[0][j] = 0;
			}
		}
		for(int i = 1; i < m; i++){
			for(int j = 1; j < n; j++){
				if(obstacleGrid[i][j] == 1){
					dp[i][j] = 0;
				}else{
					dp[i][j] = dp[i-1][j] + dp[i][j-1];
				}
			}
		}

		return dp[m-1][n-1];
    }
	
};

int main(){
	Solution so;
	int m = 3;
	int n = 2;
	int a = so.uniquePaths(m, n);
	cout << a << endl;
	return 0;
}